The performance of anytime algorithms can be improved by simultaneouslysolving several instances of algorithm-problem pairs. These pairs may includedifferent instances of a problem (such as starting from a different initialstate), different algorithms (if several alternatives exist), or several runsof the same algorithm (for non-deterministic algorithms). In this paper wepresent a methodology for designing an optimal scheduling policy based on thestatistical characteristics of the algorithms involved. We formally analyze thecase where the processes share resources (a single-processor model), andprovide an algorithm for optimal scheduling. We analyze, theoretically andempirically, the behavior of our scheduling algorithm for various distributiontypes. Finally, we present empirical results of applying our schedulingalgorithm to the Latin Square problem.
展开▼
